package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description TODO
 *
 * @ClassName algorithm.sort.MergeSort
 * @Version 1.0
 * @Date: 2022/2/16 11:33
 * @Author xuyi
 */
public class MergeSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        mergeSort(arr,0,arr.length-1);
    }
    private void mergeSort(int[] arr,int l,int r){
        int[] res = null;
        if(l>=r){
            return;
        }
        int mid = l+((r-l)>>1);
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        sortInL_R(arr,l,r);
    }

    private void sortInL_R(int[] arr,int l,int r){
        int mid = l+((r-l)>>1);
        int lLength = mid-l+1;
        int[] tempArr = Arrays.copyOfRange(arr, l, r + 1);
        int idx=l;
        int i=0,j=lLength;
        while(j<tempArr.length&&i<lLength){
            if(tempArr[i] > tempArr[j]){
                arr[idx++]=tempArr[j++];
            }
            else{
                arr[idx++]=tempArr[i++];
            }
        }
        while(i<lLength){
            arr[idx++]=tempArr[i++];
        }
        while(j<tempArr.length){
            arr[idx++]=tempArr[j++];
        }
    }
}
